/**
 * 
 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 */


/**
 * @think 利用栈和贪心算法的思想
 *        1. 维护一个栈stack，
 *        2. 遍历字符串，对每个字符char，首先判断stack中是否存在，
 *          2.1 若stack栈顶值比char大且后续还存在此值，则将栈顶弹出；
 *            2.1.1 使用indexOf(xx, i)取代 lastIndexOf(xx)减少遍历次数会更快
 *        3. 否则，入栈每个char
 *        4. 打印栈底到栈顶即为结果n
 * @time O(nlogn) 
 * @space 0(n) 只需借用一个栈
 * @param {string} s
 * @return {string} s
 * 
 *  示例 1：

    输入：s = "bcabc"
    输出："abc"
    示例 2：

    输入：s = "cbacdcbc"
    输出："acdb"
 */



var removeDuplicateLetters = function (s) {
  let len = s.length;
  let stack = []
  for (let i = 0; i < len; i++) {
    let c = s[i];
    if (stack.indexOf(c) !== -1) continue;
    while (stack.length && stack[stack.length - 1] > c && s.indexOf(stack[stack.length - 1], i) !== -1) {
      stack.pop();
    }
    stack.push(c);
  }
  return stack.join("");
};

